#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    static const int N = 60;
    int dp[N][N] = { 0 };
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    void dfs(vector<vector<int>>& moveTime, int i, int j, int cost)
    {
        if (cost >= dp[i][j] && dp[i][j] != 0)
            return;
        if ((i != 0 || j != 0) && cost <= moveTime[i][j])
            cost = moveTime[i][j] + 1;
        dp[i][j] = cost;
        int n = moveTime.size(), m = moveTime[0].size();
        for (int k = 0; k < 4; k++)
        {
            int a = dx[k] + i;
            int b = dy[k] + j;
            if (a >= 0 && a < n && b >= 0 && b < m)
            {
                dfs(moveTime, a, b, cost + 1);
            }
        }
    }
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(), m = moveTime[0].size();
        dfs(moveTime, 0, 0, 0);
        return dp[n - 1][m - 1];
    }
};